Tham khảo Bài_toán_P_so_với_NP

  1. ↑ Cook, Stephen (1971). “The complexity of theorem proving procedures”. Proceedings of the Third Annual ACM Symposium on Theory of Computing. tr. 151–158. 
  2. ↑ Lance Fortnow, The status of the P versus NP problem, Communications of the ACM 52 (2009), số. 9, tr. 78–86. doi:10.1145/1562164.1562186
Các lớp độ phức tạp quan trọng (thêm)
Các lớp được coi là giải được
DLOGTIME • AC0 • ACC0 • TC0 • L • SL • RL • NL • NC • SC • P (P-đầy đủ) • ZPP • RP • BPP • BQP 
Các lớp có thể không giải được
Các lớp được coi là không giải được
EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL
Các hệ thống cấp bậc
Các nhóm các lớp độ phức tạp